package com.shixianjun.leetcode;

import java.util.HashMap;

public class _1_两数之和 {

    static public int[] twoSum(int[] nums, int target) {
        /**
         * 第一想法 双重遍历 暴力美学
         * */

        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{0};
    }

    static public int[] twoSum2(int[] nums, int target) {
        /**
         * 优化 动态规划 哈希表 空间换时间
         * */

        HashMap<Integer, Integer> hashTable = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; i++) {
            Integer value = target - nums[i];
            if (hashTable.containsKey(value)) {
                return new int[]{hashTable.get(value), i};
            } else {
                hashTable.put(nums[i], i);
            }
        }
        return new int[]{0};
    }

    static public int[] twoSum3(int[] nums, int target) {
        /**
         * 优化 动态规划 哈希表 空间换时间 双向指针
         * */

        HashMap<Integer, Integer> hashTable = new HashMap<Integer, Integer>();

        for (int i = 0, j = nums.length - 1; i <= j; i++, j--) {
            Integer valuei = target - nums[i];
            if (hashTable.containsKey(valuei)) {
                return new int[]{hashTable.get(valuei), i};
            } else {
                hashTable.put(nums[i], i);
            }

            Integer valuej = target - nums[j];
            if (hashTable.containsKey(valuej)) {
                return new int[]{hashTable.get(valuej), j};
            } else {
                hashTable.put(nums[j], j);
            }
        }
        return new int[]{0};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int[] indexs = twoSum3(nums, 9);
        if (indexs.length == 2) {
            System.out.print(indexs[0] + " " + indexs[1]);
        } else {
            System.out.print("未找到");
        }
    }
}
